class Solution(object):
    def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
        """
        :type jug1Capacity: int
        :type jug2Capacity: int
        :type targetCapacity: int
        :rtype: bool
        """
        if jug1Capacity == targetCapacity or jug2Capacity == targetCapacity or jug1Capacity + jug2Capacity == targetCapacity:
            return True
        already_set = {(0, 0)}
        now_set = {(jug1Capacity, 0), (0, jug2Capacity)}

        def find_next(x, y):
            out = [(0, y), (x, 0), (jug1Capacity, y), (x, jug2Capacity)]
            if x >= jug2Capacity - y:
                out.append((x + y - jug2Capacity, jug2Capacity))
            else:
                out.append((0, x + y))
            if y >= jug1Capacity - x:
                out.append((jug1Capacity, x + y - jug1Capacity))
            else:
                out.append((x + y, 0))
            return out
        while now_set:
            already_set.update(now_set)
            next_set = set()
            for x, y in now_set:
                for ux, uy in find_next(x, y):
                    if (ux, uy) not in already_set:
                        if ux == targetCapacity or uy == targetCapacity or ux + uy == targetCapacity:
                            return True
                        else:
                            next_set.add((ux, uy))
            now_set = next_set
        return False


data = Solution()
jug1Capacity = 3
jug2Capacity = 5
targetCapacity = 4
print(data.canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity))
jug1Capacity = 1
jug2Capacity = 2
targetCapacity = 3
print(data.canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity))
jug1Capacity = 2
jug2Capacity = 6
targetCapacity = 5
print(data.canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity))